/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode Node;
Node* append(Node *list, int val) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->val = val;
    p->next = NULL;
    
    if (list == NULL) {
        return p;
    }
    
    Node *t = list;
    while (t->next != NULL) {
        t = t->next;
    }    
    t->next = p;
    
    return list;
}

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    Node *mergeList = NULL;
    Node *p1 = l1;
    Node *p2 = l2;
    
    while (p1 != NULL || p2 != NULL) {
        if (p1 != NULL && p2 != NULL) {
            if (p1->val < p2->val) {
                mergeList = append(mergeList, p1->val);
                p1 = p1->next;
            } else {                
                mergeList = append(mergeList, p2->val);
                p2 = p2->next;
            }
        } else if (p1 != NULL && p2 == NULL) {            
            mergeList = append(mergeList, p1->val);
            p1 = p1->next;
        } else if (p1 == NULL && p2 != NULL) {                        
            mergeList = append(mergeList, p2->val);
            p2 = p2->next;
        }
    }
    
    return mergeList;
}

